package com.sourcetrip.algorithm.sort.merge;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

/**
 * @author: ZhouBert
 * @date: 2020/12/31
 * @description: 十大排序算法之五：归并排序（的对象比较版本） --
 * V1 针对 V0 进行空间优化 + 递归改迭代！
 * 虽然 1KW 的数据，也才 26层。
 * 但是把 归并排序从递归改成迭代练手也是不错的。
 */
public class MergeCustomedSortV1<E> extends AbstractCustomedObjectSort<E> {

    /**
     * 1.空间优化：
     * 保留一个最大的数组，避免频繁创建数组。
     */
    private E[] leftArr = null;

    @Override
    protected void sortArr(E[] objectArr) {
        leftArr = (E[]) new Object[objectArr.length];
        int end = 0, interval = 0, lastIndex = 0, lastEnd = objectArr.length - 1;

        for (int weight = 2; weight < objectArr.length; weight *= 2) {
            end = objectArr.length - weight;
            interval = weight >> 1;
            for (int i = 0; i <= end; i += weight) {
                //merge(objectArr, i, i + interval, (i + weight > objectArr.length) ? objectArr.length : i + weight);
                merge(objectArr, i, i + interval, i + weight);
                lastIndex = i;
            }
            //处理最后一组
            //判断条件：上面的条件最后一组处理完以后的 lastIndex+weight 是否小于 objectArr.length
            //谨记 [begin,end) 的设计！！！
            if (lastIndex + weight < objectArr.length) {
                //还需要处理最后一组
                //最后一组 [lastIndex,lastIndex + weight) 已经有序
                //[lastIndex + weight,objectArr.length) 已经有序
                merge(objectArr, lastIndex, lastIndex + weight, objectArr.length);
            }
        }
        //最后一组的合并忘了，但是递归时是怎么处理这个问题的呢？？？

    }


    private void merge(E[] objectArr, int begin, int mid, int end) {
        int leftSize = mid - begin;
        //1.将 left 部分迁移到 leftTemp 上
        System.arraycopy(objectArr, begin, leftArr, 0, leftSize);
        //设置几个索引
        int lb = 0;
        int rb = mid;
        //当 lb 和 rb 仍有空余
        while (lb < leftSize && rb < end) {
            if (compare(leftArr[lb], objectArr[rb]) > 0) {
                objectArr[begin] = objectArr[rb++];
            } else {
                objectArr[begin] = leftArr[lb++];
            }
            begin++;
        }
        //此时 left arr 放置完毕
        if (lb == leftSize) {
            //将剩下的 objectArr 中的放进去，其实就不需要动了！因为本来就在里面！
        }
        if (rb == end) {
            //将 left arr 中的元素覆盖 object arr
            while (lb < leftSize) {
                objectArr[begin++] = leftArr[lb++];
            }
        }
    }
}
